package cn.xkai.exercise.b;

/**
 * @description: 缺失数字
 * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数
 * 自己的思路：计数法
 * 借鉴的思路：异或运算-O(n)
 * @author: kaixiang
 * @date: 2022-07-15
 **/
public class Solution64 {
    public int missingNumber(int[] nums) {
        int[] temp = new int[nums.length + 1];
        for (int num : nums) {
            temp[num] = 1;
        }
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    public int missingNumberXor(int[] nums) {
        int reduce = 0;
        for (int i = 0; i < nums.length; i++) {
            reduce ^= nums[i] ^ i;
        }
        return reduce ^ nums.length;
    }

    public int missingNumber_等差数列(int[] nums) {
        int sum = (1 + nums.length) * (nums.length + 1) / 2;
        for (int num : nums) {
            sum -= num;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {3, 0, 1};
        Solution64 solution64 = new Solution64();
        System.out.println(solution64.missingNumber(nums));
    }
}
